﻿#pragma once
#include "stdafx.h"

//给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
//两个相邻元素间的距离为 1 。
//示例 1:
//输入:
//0 0 0
//0 1 0
//0 0 0
//输出 :
//	0 0 0
//	0 1 0
//	0 0 0
//	示例 2 :
//	输入 :
//	0 0 0
//	0 1 0
//	1 1 1
//	输出 :
//	0 0 0
//	0 1 0
//	1 2 1
//	注意 :
//
//	给定矩阵的元素个数不超过 10000。
//	给定矩阵中至少有一个元素是 0。
//	矩阵中的元素只在四个方向上相邻 : 上、下、左、右。
//
//	来源：力扣（LeetCode）
//	链接：https ://leetcode-cn.com/problems/01-matrix
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
	//计算一个点到最近的0的距离
	int GetDistanceToZero(int x, int y, const vector<vector<int>>& matrix)
	{
		if (matrix[x][y] == 0)
			return 0;
		int distance = 1;		//当前寻找的距离
		//按距离从近到远寻找
		while (distance <= matrix.size() + matrix[0].size())
		{
			//查找第一象限，第一象限中距离相同的点的一次函数为y=-x+distance(0<=x<=distance)
			for (int x_offset = 0; x_offset <= distance; x_offset++)
			{
				int y_offset = distance - x_offset;
				int point_x = x + x_offset;
				int point_y = y + y_offset;
				if (point_x < 0 || point_x >= matrix.size())
					continue;
				if (point_y < 0 || point_y >= matrix[0].size())
					continue;
				if (matrix[point_x][point_y] == 0)			//找到一个0，则当前距离就是最近的距离
					return distance;
			}
			//查找第二象限，第二象限中距离相同的点的一次函数为y=x+distance(-distance<=x<=0)
			for (int x_offset = -distance; x_offset <= 0; x_offset++)
			{
				int y_offset = x_offset + distance;
				int point_x = x + x_offset;
				int point_y = y + y_offset;
				if (point_x < 0 || point_x >= matrix.size())
					continue;
				if (point_y < 0 || point_y >= matrix[0].size())
					continue;
				if (matrix[point_x][point_y] == 0)			//找到一个0，则当前距离就是最近的距离
					return distance;
			}
			//查找第三象限，第三象限中距离相同的点的一次函数为y=-x-distance(-distance<=x<=0)
			for (int x_offset = -distance; x_offset <= 0; x_offset++)
			{
				int y_offset = -x_offset - distance;
				int point_x = x + x_offset;
				int point_y = y + y_offset;
				if (point_x < 0 || point_x >= matrix.size())
					continue;
				if (point_y < 0 || point_y >= matrix[0].size())
					continue;
				if (matrix[point_x][point_y] == 0)			//找到一个0，则当前距离就是最近的距离
					return distance;
			}
			//查找第四限，第四象限中距离相同的点的一次函数为y=x-distance(0<=x<=distance)
			for (int x_offset = 0; x_offset <= distance; x_offset++)
			{
				int y_offset = x_offset - distance;
				int point_x = x + x_offset;
				int point_y = y + y_offset;
				if (point_x < 0 || point_x >= matrix.size())
					continue;
				if (point_y < 0 || point_y >= matrix[0].size())
					continue;
				if (matrix[point_x][point_y] == 0)			//找到一个0，则当前距离就是最近的距离
					return distance;
			}

			distance++;
		}
		return -1;
	}

	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
		vector<vector<int>> result = matrix;
		for (int i = 0; i < result.size(); i++)
		{
			for (int j = 0; j < result[i].size(); j++)
			{
				result[i][j] = GetDistanceToZero(i, j, matrix);
			}
		}
		return result;
	}
};

void PrintMatrix(const vector<vector<int>>& matrix)
{
	for (int i = 0; i < matrix.size(); i++)
	{
		std::cout << '[';
		for (int j = 0; j < matrix[i].size(); j++)
		{
			std::cout << matrix[i][j] << ',';
		}
		std::cout << ']' << std::endl;
	}
}

void TextMatrix()
{
	//vector<vector<int>> matrix{ {0, 0, 0},
	//{0, 1, 0},
	//{1, 1, 1} };

	vector<vector<int>> matrix{
		{ 1,0,1,1,0,0,1,0,0,1 },
		{ 0,1,1,0,1,0,1,0,1,1 },
		{ 0,0,1,0,1,0,0,1,0,0 },
		{ 1,0,1,0,1,1,1,1,1,1 },
		{ 0,1,0,1,1,0,0,0,0,1 },
		{ 0,0,1,0,1,1,1,0,1,0 },
		{ 0,1,0,1,0,1,0,0,1,1 },
		{ 1,0,0,0,1,1,1,1,0,1 },
		{ 1,1,1,1,1,1,1,0,1,0 },
		{ 1,1,1,1,0,1,0,0,1,1 } };

	Solution solution;
	auto res = solution.updateMatrix(matrix);
	PrintMatrix(res);

	//int n = solution.GetDistanceToZero(8, 0, matrix);
	int a = 0;
	system("pause");
}

//输入
//[[1,0,1,1,0,0,1,0,0,1],[0,1,1,0,1,0,1,0,1,1],[0,0,1,0,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,1],[0,1,0,1,1,0,0,0,0,1],[0,0,1,0,1,1,1,0,1,0],[0,1,0,1,0,1,0,0,1,1],[1,0,0,0,1,1,1,1,0,1],[1,1,1,1,1,1,1,0,1,0],[1,1,1,1,0,1,0,0,1,1]]
//输出
//[[1,0,1,1,0,0,1,0,0,1],[0,1,1,0,1,0,1,0,1,1],[0,0,1,0,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,1],[0,1,0,1,1,0,0,0,0,1],[0,0,1,0,1,1,1,0,1,0],[0,1,0,1,0,1,0,0,1,1],[1,0,0,0,1,1,1,1,0,1],[1,1,1,1,1,2,1,0,1,0],[3,2,2,1,0,1,0,0,1,1]]
//预期
//[[1,0,1,1,0,0,1,0,0,1],[0,1,1,0,1,0,1,0,1,1],[0,0,1,0,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,1],[0,1,0,1,1,0,0,0,0,1],[0,0,1,0,1,1,1,0,1,0],[0,1,0,1,0,1,0,0,1,1],[1,0,0,0,1,2,1,1,0,1],[2,1,1,1,1,2,1,0,1,0],[3,2,2,1,0,1,0,0,1,1]]

